package datastructure
{
	import data.AppConfig;

	/**
	 * 图类 
	 * @author juxuan
	 * 
	 */	
	public class Graph
	{
		private var numVertex:int;	//顶点数量
		private var numEdge:int;	//边的数量
		public var matrix:Array;	//邻接矩阵
		private var mark:Array;	//标志数组
		
		
		public function Graph(numVert:int)
		{
			var i:int,j:int;
			this.numVertex = numVert;
			this.numEdge = 0;
			this.mark = new Array(numVert);
			for(i = 0;i < numVert; i++)
			{
				this.mark[i] = AppConfig.UNVISITED;
			}
			
			this.matrix = new Array(numVert);
			for(i = 0;i < numVert; i++)
			{
				this.matrix[i] = new Array(numVert);
			}
			
			for(i = 0;i < numVert; i++)
			{
				for(j = 0;j < numVert;j++)
				{
					this.matrix[i][j] = 0;
				}
			}
							
		}
		
		/**
		 * 返回顶点数量 
		 * @return 
		 * 
		 */		
		public function verNum():int
		{
			return this.numVertex;
		}
		
		/**
		 * 返回边的数量 
		 * @return 
		 * 
		 */		
		public function edgeNum():int
		{
			return this.numEdge;
		}
		
		/**
		 * 返回给点顶点的第一个邻居顶点的下标 
		 * @param v
		 * @return 
		 * 
		 */		
		public function firstNeigbor(v:int):int
		{
			var i:int;
			for(i = 0;i < this.numVertex;i++)
			{
				if(this.matrix[v][i] != 0)
					return i;
			}
			
			return i;
		}
		
		/**
		 * 返回v1的在v2之后的邻居
		 * @param v1
		 * @param v2
		 * @return 
		 * 
		 */		
		public function nextNeigbor(v1:int,v2:int):int
		{
			var i:int;
			for(i = v2 + 1; i < this.numVertex; i++)
			{
				if(this.matrix[v1][i] != 0)
					return i;
			}
			
			return i;
		}
		
		
		/**
		 * 存储一条边 
		 * @param v1
		 * @param v2
		 * @param w
		 * 
		 */				
		public function setEdge(v1:int,v2:int,w:int):void
		{
			if(w <= 0)
			{
				trace("非法权值输入");
				return;
			}
			if(this.matrix[v1][v2] == 0)
				this.numEdge ++;
			
			this.matrix[v1][v2] = w;
		}
		
		/**
		 * 删除一条边 
		 * @param v1
		 * @param v2
		 * 
		 */		
		public function delEdge(v1:int,v2:int):void
		{
			if(this.matrix[v1][v2] != 0)
				this.numEdge --;
			
			this.matrix[v1][v2] = 0;
		}
		
		/**
		 * 返回两个顶点之间的边的权重，如果不存在改边，则返回0 
		 * @param v1
		 * @param v2
		 * @return 
		 * 
		 */		
		public function weight(v1:int,v2:int):int
		{
			return this.matrix[v1][v2];
		}
		
		/**
		 * 返回 给点顶点的标志
		 * @param v
		 * @return 
		 * 
		 */		
		public function getMark(v:int):int
		{
			return this.mark[v];
		}
		
		
		/**
		 * 设置顶点的标志 
		 * @param v
		 * @param mark
		 * 
		 */		
		public function setMark(v:int,mark:int):void
		{
			this.mark[v] = mark;
		}
		
		
		/**
		 *释放占用的地址空间 
		 * 
		 */		
		public function dispose():void
		{
			this.mark = null;
			for(var i:int = 0;i < this.numVertex; i++)
			{
				this.matrix[i] = null;
			}
			this.matrix = null;
		}
		
		
		
	}
}